# 介绍
散列表也称哈希表，本质上是利用了数组支持按照下标随机访问的特性。基本元素是由键（Key）和值（Value）组成的键值对，通过散列函数将 Key 映射为下标，将 Value 存储在数组中对应下标的位置
# 散列函数
- 简单高效
- 分布均匀
实际使用中，应当根据 Key 的长度、特点、分布以及散列表的大小等特点设计散列函数。如要对手机号进行散列，可以使用手机号后 4 位作为散列值，因为号码前几位重复较多；又比如如果要对英文单词进行散列，可以对每个字母进行编码，如转换为对应的编号（0 - 26），组成一个 26 进制的数值，之后转换为 10 进制对散列表大小进行取模运算
# 动态扩容
装载因子：散列表中已经插入的元素数量占散列表大小的比例
装载因子越大，散列表中空闲位置越小，散列冲突的可能性越大。因此可以设置一个阈值，当装载因子超过阈值时，对散列表进行动态扩容
每次扩容后，对已经插入散列表的元素，都需要重新计算散列值，因此插入一个数据，最差时间复杂度为 O(n)，最好时间复杂度为 O(1)，经过摊还分析，平均复杂度为 O(1)。
尽管平均复杂度为 O(1)，当散列表大小已经很大时（如 1 G），这种「一次性」扩容操作就需要消耗大量时间，十分低效。解决方案是采用「多次」扩容：当装载因子触及阈值时，只申请新的空间，但不立刻进行数据搬迁，每当有新数据插入，直接插入新的散列表，与此同时搬迁一个旧数据到新散列表中，这样经过多次操作，旧散列表就完全搬迁到新表中去了。查询时，先查询旧表，查询不到再去新表查询即可。
# 散列冲突解决
# 开放寻址法
- 插入：如果发现位置已被占用，继续探测寻找表中空闲位置
- 查找：通过 Key 求出散列值后，比较对应元素的 Key 是否与要查找的 Key 相同，如相同则已经找到，如不同则继续探测寻找，遇到第一个空闲位置时停止（可知元素不存在）
- 删除：不能仅仅将删除元素置空，因为可能会导致查找出错，可以将删除的元素标记为 deleted
提示
三种探测方式
- 线性探测：hash(key)+0, hash(key)+1, hash(key)+2,...
- 二次探测：hash(key)+0, hash(key)+1^2, hash(key)+2^2,...
- 双重散列：hash1(key), hash2(key), hash3(key),...
查找时，如果以遇到空闲作为终止条件
- 给定 A 和 B 都映射到下标 X 上，A 先插入散列表，则 A 占据位置 X
- B 接着插入散列表，占据位置 X + 1
- 删除 A，将 X 置空
- 此时如果查找 B，则会误判 B 不存在
# 链表法
使用链表法时，数组的每个位置可以视为一个「槽」，每个「槽」对应一条链表，当插入元素时，根据其散列值，找到对应的「槽」，将元素插入即可
此时插入时间复杂度为 O(1)，而查找、删除元素的复杂度取决于链表的长度 K，即 O(K)
散列表碰撞攻击
通过精心设置的数据，使得所有数据经过散列后，都散列到同一位置，导致散列表退化为链表（链表法），查询复杂度由 O(1) 退化为 O(n)，这样查询操作消耗大量 CPU 或者线程资源，系统无法响应其他请求，造成拒绝式服务攻击（DoS）
# 开放寻址与链表法比较
开放寻址：适合数据量小，装载因子小，例子： ThreadLocalMap
- 数据都存储在数组中，可以有效利用 CPU 缓存加快查询
- 方便序列化（链表法包含指针，不容易序列化）
- 删除数据较为麻烦，需要标记 delete
- 所有数据都存储在数组，冲突的代价更高，因此装载因子不能太高，空间利用率差
链表法：适合数据量大，存储大对象，更加灵活，支持优化策略，例子： LinkedHashMap
- 结点可以在需要时创建，空间利用率更高
- 对装载因子的容忍度更高（只要分布均匀，大于 1 也可以）
- 存储需要指针，对于较小的对象来说，会浪费内存空间，且结点在内存中不连续，缓存不友好
- 链表法还可以改进，将链表结构换成其他更高效的数据结构（如跳表、红黑树），这样在极端情况下，所有数据被散列到同一个槽中，复杂度也只会退化为 O(logn)，避免了碰撞攻击
# 散列表与链表
散列表常常与（双向）链表配合适用：散列表支持高效的插入、删除、查找，但是散列表中的数据都是被散列函数打乱之后无序存储的，因此当希望顺序遍历散列表中的数据时，常常结合链表（或跳表）一起使用